home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 26 / Cream of the Crop 26.iso / os2 / octa209b.zip / octave-2.09 / SCRIPTS.ZIP / scripts.fat / elfun / gcd.m < prev    next >
Text File  |  1997-03-08  |  2KB  |  64 lines
  1. ## Copyright (C) 1996 John W. Eaton
  2. ##
  3. ## This file is part of Octave.
  4. ##
  5. ## Octave is free software; you can redistribute it and/or modify it
  6. ## under the terms of the GNU General Public License as published by
  7. ## the Free Software Foundation; either version 2, or (at your option)
  8. ## any later version.
  9. ##
  10. ## Octave is distributed in the hope that it will be useful, but
  11. ## WITHOUT ANY WARRANTY; without even the implied warranty of
  12. ## MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13. ## General Public License for more details.
  14. ##
  15. ## You should have received a copy of the GNU General Public License
  16. ## along with Octave; see the file COPYING.  If not, write to the Free
  17. ## Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  18. ## 02111-1307, USA.
  19.  
  20. ## usage: gcd (a, ...)
  21. ##
  22. ## [g [, v]] = gcd (a) returns the greatest common divisor g of the
  23. ## entries of the integer vector a, and an integer vector v such that
  24. ## g = v(1) * a(k) + ... + v(k) * a(k).
  25. ##
  26. ## [g [, v]] = gcd (a1, ..., ak) is the same with a = [a1, ..., ak].
  27.  
  28. ## Author: KH <Kurt.Hornik@ci.tuwien.ac.at>
  29. ## Created: 16 September 1994
  30. ## Adapted-By: jwe
  31.  
  32. function [g, v] = gcd (a, ...)
  33.  
  34.   if (nargin == 0)
  35.     usage ("[g, v] = gcd (a, ...)");
  36.   endif
  37.  
  38.   if (nargin > 1)
  39.     va_start;
  40.     for k = 2:nargin;
  41.       a = [a, (va_arg ())];
  42.     endfor
  43.   endif
  44.  
  45.   if (round (a) != a)
  46.     error ("gcd: all arguments must be integer");
  47.   endif
  48.  
  49.   g = abs (a(1));
  50.   v = sign (a(1));
  51.   for k = 1:(length (a) - 1)
  52.     x = [g, 1, 0];
  53.     y = [(abs (a(k+1))), 0, 1];
  54.     while (y(1) > 0)
  55.       r = x - y * floor (x(1) / y(1));
  56.       x = y;
  57.       y = r;
  58.     endwhile
  59.     g = x(1);
  60.     v = [x(2) * v, x(3) * (sign (a(k+1)))];
  61.   endfor
  62.  
  63. endfunction
  64.